0873. 最长的斐波那契子序列的长度【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 暴力解法

1. 📝 题目描述

• leetcode

如果序列 x1, x2, ..., xn 满足下列条件，就说它是 斐波那契式 的：

• n >= 3
• 对于所有 i + 2 <= n，都有 xi + xi+1 == xi+2

给定一个 严格递增 的正整数数组形成序列 arr，找到 arr 中最长的斐波那契式的子序列的长度。如果不存在，返回 0。

子序列 是通过从另一个序列 arr 中删除任意数量的元素（包括删除 0 个元素）得到的，同时不改变剩余元素顺序。例如，[3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的子序列。

---

示例 1：

输入: arr = [1,2,3,4,5,6,7,8]
输出: 5
解释: 最长的斐波那契式子序列为 [1,2,3,5,8]。

示例 2：

输入: arr = [1,3,7,11,12,14,18]
输出: 3
解释: 最长的斐波那契式子序列有 [1,11,12]、[3,11,14] 以及 [7,11,18]。

---

提示：

• 3 <= arr.length <= 1000
• 1 <= arr[i] < arr[i + 1] <= 10^9

2. 🎯 s.1 - 暴力解法

js

/**
 * 找到数组中最长的斐波那契子序列的长度
 * 斐波那契子序列：满足斐波那契规律的子序列，即 arr[i] + arr[j] = arr[k] (i < j < k)
 * @param {number[]} arr - 严格递增的正整数数组
 * @return {number} 最长斐波那契子序列的长度
 */
var lenLongestFibSubseq = function (arr) {
  const n = arr.length
  // 使用 Map 存储值到索引的映射，便于快速查找
  const indexMap = new Map()
  for (let i = 0; i < n; i++) {
    indexMap.set(arr[i], i)
  }

  // dp[i][j] 表示以 arr[i] 和 arr[j] 作为最后两个元素的斐波那契子序列的长度
  const dp = Array(n)
    .fill(null)
    .map(() => Array(n).fill(2))

  let maxLen = 0

  // 遍历所有可能的斐波那契序列的最后两个元素
  for (let k = 2; k < n; k++) {
    for (let j = 1; j < k; j++) {
      // 计算前一个元素的值
      const prev = arr[k] - arr[j]

      // 检查这个值是否存在于数组中，并且索引小于 j
      if (indexMap.has(prev)) {
        const i = indexMap.get(prev)
        if (i < j) {
          // 更新以 arr[i] 和 arr[j] 作为最后两个元素的斐波那契子序列的长度
          dp[j][k] = dp[i][j] + 1
          maxLen = Math.max(maxLen, dp[j][k])
        }
      }
    }
  }

  // 如果最大长度小于3，说明没有找到有效的斐波那契子序列
  return maxLen >= 3 ? maxLen : 0
}